#include "Graph.h"
#include <iostream>
#include <sys/time.h> 
#include <omp.h>
#include <unordered_set>
#include <algorithm>
using namespace std;

template <class T1, class T2>
struct dist_smaller{
	bool operator() (const pair<T1,T2>& x, const pair<T1,T2>& y) const {return x.second < y.second;}
};

Graph::Graph(int _num_partition_file, int _num_true_partitions, string in_dir){
	this->num_partitions = _num_true_partitions;
	
	LoadAdjGraph(this->adj_lists,in_dir);
	num_nodes = adj_lists.size();

	if(_num_true_partitions != LoadGraphPartition(this->node_partition_map,in_dir,_num_partition_file)){
		cout << "error in partition loading, true partition not equal to unique partitions" << endl;
		exit(1);
	}
	LoadPartitionDistAndPivots(this->partition_dist,this->pivot_nodes,this->pivot_to_all_dist,in_dir,num_nodes,num_partitions);

	Load2HopNN(this->nn2hop,in_dir);
	if(this->nn2hop.size() != num_nodes){
		cout << "nearest 2 hop neighbour the size does not match: " <<nn2hop.size() << " vs. " << num_nodes << endl;
		exit(1);
	}

	// need to compute max distance
	FindMaxSocialDistance();

	#pragma omp parallel for
	for(int i = 0; i < this->adj_lists.size(); i++){
		sort(adj_lists[i].begin(),adj_lists[i].end(),dist_smaller<int,int>());
	}

	for(int i = 0; i < num_nodes; i++){
		this->node_degree_rank.push_back(make_pair(this->adj_lists[i].size(),i));
	}
	sort(node_degree_rank.begin(),node_degree_rank.end());
}

int Graph::SampleUser(int degree_level){
	
	int stride = this->num_nodes / 4;
	if(degree_level == 2) degree_level++;
	return node_degree_rank[stride * degree_level + rand()%stride].second;
}

void Graph::FindMaxSocialDistance(){
	int min_max_dist = 1000000;
	int max_max_dist = -1;
	for(int i = 0; i < this->pivot_to_all_dist.size(); i++){
		int max_dist = -1;
		for(int j = 0; j < this->pivot_to_all_dist[i].size(); j++){
			if(pivot_to_all_dist[i][j] > max_dist){
				max_dist = pivot_to_all_dist[i][j];
			}
		}
		if(max_max_dist < max_dist) max_max_dist = max_dist;
		if(min_max_dist > max_dist) min_max_dist = max_dist;
	}
	this->max_social_distance = max_max_dist+100;
	cout << "max max dist: " << max_max_dist << endl;
	cout << "min max dist: " << min_max_dist << endl;

}

void Graph::InitPointTranverse(int node){
	timeval t1, t2;
	gettimeofday(&t1, NULL);


	source_node = node;
	dist_from_user.clear();
	dist_determined.clear();
	not_finalized_nodes.clear();
	not_finalized_nodes.resize(this->max_social_distance);

	vec_pos = 0;
	social_rel.clear();
	minimum_dist_so_far = 0;
	max_rel_so_far = 1;

	dist_from_user.resize(this->num_nodes,1000000); // this value must be samll than the maximum distance
	dist_determined.resize(this->num_nodes,false);
	social_rel.resize(this->num_nodes,-1);

	dist_from_user[node] = 0;

	node_processed = 0;
	elapsedTime = 0;

	// check if this node is a pivot
	int pivot_idx = -1;
	for(int i = 0; i < this->num_partitions; i++) {
		if(node == this->pivot_nodes[i]){
			pivot_idx = i;
			break;
		}
	}

	if(pivot_idx > 0){
		for(int i = 0; i < this->num_nodes; i++){
			dist_from_user[i] = this->pivot_to_all_dist[pivot_idx][i];
			dist_determined[i] = true;
			social_rel[i] = (double)1.0 - (double)dist_from_user[i]/this->max_social_distance;
		}
		return;
	}

	// add pivot in the tranverse queue
	node_processed = num_partitions; // as k elements has been processed
	
	//for(int i = 0; i < this->num_partitions; i++){
	//	// update neigbour info
	//	int pivot_idx = this->pivot_nodes[i];
	//	int source2pivot = this->pivot_to_all_dist[i][node];
	//	for(int j = 0; j < this->num_nodes; j++){
	//		int dist =  this->pivot_to_all_dist[i][j] + source2pivot;
	//		if(dist < dist_from_user[j]) dist_from_user[j] = dist;
	//	}
	//	dist_determined[pivot_idx] = true;
	//	dist_from_user[pivot_idx] = source2pivot;
	//	social_rel[pivot_idx] =  (double)(this->max_social_distance-dist_from_user[pivot_idx])/this->max_social_distance;
	//}
	

	#pragma omp parallel for
	for(int i = 0; i < this->num_nodes; i++){
		for(int part = 0; part < this->num_partitions; part++){
			int dist = this->pivot_to_all_dist[part][node] + this->pivot_to_all_dist[part][i];
			if(dist < dist_from_user[i]) dist_from_user[i] = dist;
		}
	}
	for(int i = 0; i < this->num_partitions; i++){
		int pivot_idx = this->pivot_nodes[i];
		int source2pivot = this->pivot_to_all_dist[i][node];
		dist_determined[pivot_idx] = true;
		dist_from_user[pivot_idx] = source2pivot;
		social_rel[pivot_idx] =  (double)(this->max_social_distance-dist_from_user[pivot_idx])/this->max_social_distance;
	}


	// initialize the set
	int num_invalid = 0;
	for(int i = 0; i < num_nodes; i++){
		if(dist_determined[i]) continue;
		if(dist_from_user[i] >= this->max_social_distance){
			num_invalid++;
			continue;
		}
		not_finalized_nodes[dist_from_user[i]].push_back(i);
	}

	this->target_node_neighbour.resize(num_nodes,make_pair(-1,-1));

	gettimeofday(&t2, NULL);
	// compute and print the elapsed time in millisec
	elapsedTime += (t2.tv_sec - t1.tv_sec) * 1000.0;      // sec to ms
	elapsedTime += (t2.tv_usec - t1.tv_usec) / 1000.0;   // us to2 ms
	cout << "time spend for computing pivot estimate: " << elapsedTime << endl;
	cout << "number of invalid: " << num_invalid << endl;
	if(num_invalid != 0){
		cout << "a problem may occur in graph init +++++++++++++++++++++" << endl;
	}
	elapsedTime = 0;
	 //cout << "number of elimiated computations: " << eliminated_node.size() << endl;
	cout << "max social dist: " << this->max_social_distance << endl;
	
}

double Graph::GetSocialRelevance(int target_node, double min_relevance,int op_level){
	timeval t1, t2;
	gettimeofday(&t1, NULL);

	if(target_node == source_node) return -1;
	if(dist_determined[target_node]){
		if(this->social_rel[target_node] > min_relevance) return this->social_rel[target_node];
		else return -1;
	}

	int nn2hop_dist = this->nn2hop[target_node];

	if(min_relevance > max_rel_so_far) return -1;

	double result = -1;
	bool problem = true;

	int max_allowed_dist = ((double)1.0-min_relevance)*this->max_social_distance;

	if(op_level == 2){
		// assgin neighbour checking
		int min_dist = this->dist_from_user[target_node];
		for(int i = 0; i < adj_lists[target_node].size(); i++){
			int target_neighbour = adj_lists[target_node][i].first;
			this->target_node_neighbour[target_neighbour] = adj_lists[target_node][i];
			if(adj_lists[target_node][i].first == this->source_node){
				return (double)(this->max_social_distance-adj_lists[target_node][i].second)/this->max_social_distance;
			}
			int estimate = this->dist_from_user[target_neighbour] + adj_lists[target_node][i].second;
			if(estimate < min_dist) min_dist = estimate;
		}
		if(min_dist != this->dist_from_user[target_node]){
			this->dist_from_user[target_node] = min_dist;
			if(min_dist < this->max_social_distance) not_finalized_nodes[min_dist].push_back(target_node);
		}
	}
	//cout << "entered shortest path: " << endl;
	// started to tranverse
	//if(target_node == 500){
	//	cout << "it's here " << endl;
	//	cout << "nearest 2 hop for " << target_node << " is " << nn2hop_dist << endl;
	//	/*for(int i = 0; i < this->adj_lists[target_node].size(); i++){
	//		cout << adj_lists[target_node][i].first << ":" << adj_lists[target_node][i].second << " ";
	//	}
	//	cout << endl;*/
	//	cout << "num of neighbours: " <<  this->adj_lists[target_node].size() << endl;
	//	cout << "nearest two hop nearest for source: " << this->source_node << " is: " << this->nn2hop[source_node] << endl;

	//	for(int i = 0; i < this->adj_lists[68363].size(); i++){
	//		if(this->adj_lists[68363][i].first == source_node){
	//			cout << "68363 to source: " << this->adj_lists[68363][i].second << endl;
	//		}
	//		if(this->adj_lists[68363][i].first == target_node){
	//			cout << "68363 to target_node: " << this->adj_lists[68363][i].second << endl;
	//		}
	//	}

	//	for(int i = 0; i < this->adj_lists[source_node].size(); i++){
	//		if(this->adj_lists[source_node][i].first == 68363){
	//			cout << "distance to source: " << this->adj_lists[source_node][i].second << endl;
	//		}
	//	}
	//	for(int i = 0; i < this->adj_lists[target_node].size(); i++){
	//		if(this->adj_lists[target_node][i].first == 68363){
	//			cout << "distace to target: " << this->adj_lists[target_node][i].second << endl;
	//		}
	//	}
	//	cout << "68363 determined: " << this->dist_determined[68363] << endl;

	//	unordered_set<int> frontier;
	//	frontier.insert(source_node);
	//	unordered_set<int> visited;
	//	int level = 0;
	//	while(!frontier.empty()){
	//		level++;
	//		
	//		int min = 500;
	//		unordered_set<int> new_frontier;
	//		for(auto it = frontier.begin(); it != frontier.end(); it++){
	//			visited.insert(*it);
	//			for(int i = 0; i < adj_lists[*it].size(); i++){
	//				if(visited.find(adj_lists[*it][i].first) != visited.end() && adj_lists[*it][i].first != target_node) continue;
	//				if(adj_lists[*it][i].first == target_node){
	//					cout << "level: " << level << " with neighbour: " << *it << " with dist: " << adj_lists[*it][i].second << endl;
	//					int idx = 0;
	//					bool found = false;
	//					for(;idx < adj_lists[source_node].size(); idx++){
	//						if(adj_lists[source_node][idx].first == *it){
	//							found = true;
	//							break;
	//						}
	//					}
	//					if(found) cout << "found" << endl;
	//					if(min > adj_lists[*it][i].second + adj_lists[source_node][idx].second){
	//						min = adj_lists[*it][i].second + adj_lists[source_node][idx].second;
	//					}
	//					cout << "source_node: " << source_node << " to " << *it << " dist: " << adj_lists[source_node][idx].second << endl;
	//					cout << "xxxxxxxxxxxxxxxxxxxxxxxxxx" << endl;
	//					getchar();
	//				}
	//				if(visited.find(adj_lists[*it][i].first) == visited.end()) new_frontier.insert(adj_lists[*it][i].first);
	//			}
	//		}
	//		cout << "min distance so far " << min << endl;
	//		cout << "new froniter size at level: " << level << " is " << new_frontier.size() << endl;
	//		frontier = new_frontier;
	//	}
	//}
	while(node_processed != this->num_nodes){
		if(this->not_finalized_nodes[minimum_dist_so_far].size() == this->vec_pos){
			minimum_dist_so_far++;
			while(this->not_finalized_nodes[minimum_dist_so_far].size() == 0){
				minimum_dist_so_far++;
			}
			this->vec_pos = 0;
			max_rel_so_far = (double)1.0 - (double)minimum_dist_so_far/this->max_social_distance;
		}

		int best_node = not_finalized_nodes[minimum_dist_so_far][vec_pos];

		if(best_node >= this->num_nodes || minimum_dist_so_far >= this->max_social_distance){
			cout << "problem in graph tranverse" << endl;
			exit(1);
		}

		/*if(target_node == 500 && !with2hop){
			cout << "best_node: " << best_node << " with min dist: " << minimum_dist_so_far << endl;
			cout << "target_node: " << target_node << " min neighbor: " << adj_lists[target_node][0].second << " and current esimate: " << this->dist_from_user[target_node] << endl;
			getchar();
		}*/

		this->vec_pos++;
		if(dist_determined[best_node]) continue;
		node_processed++;
		
		for(int i = 0; i < this->adj_lists[best_node].size(); i++){
			int v = adj_lists[best_node][i].first;
			if(dist_determined[v]) continue;
			
			num_ops++;
			int alt = this->dist_from_user[best_node] + adj_lists[best_node][i].second;
			if(alt < this->dist_from_user[v]){
				dist_from_user[v] = alt;
				if(alt < this->max_social_distance) not_finalized_nodes[alt].push_back(v);
			}
			// with 2 hop pruning
			if(target_node_neighbour[v].first == target_node && (this->dist_from_user[v] + target_node_neighbour[v].second) < this->dist_from_user[target_node] && op_level == 2){
				this->dist_from_user[target_node] = (this->dist_from_user[v] + target_node_neighbour[v].second);
				if(dist_from_user[target_node] < this->max_social_distance) not_finalized_nodes[dist_from_user[target_node]].push_back(target_node);
			}
		}

		this->dist_determined[best_node] = true;
		this->social_rel[best_node] = max_rel_so_far;

		//minimum_dist_so_far = dist_from_user[best_node];
		if(op_level == 1){
			int dist_lower_bound = minimum_dist_so_far + adj_lists[target_node][0].second;
			double error_ratio =  (double)dist_lower_bound / dist_from_user[target_node];
			if(error_ratio >= 1.0){
				result = (double)(this->max_social_distance-dist_from_user[target_node])/this->max_social_distance;
				problem = false;
				//cout << "early terminate" << endl;
				break;
			}

			if(dist_lower_bound >= max_allowed_dist && dist_from_user[target_node] >= max_allowed_dist){
				//cout << "prunded using estimate for minimum relevance" << endl;
				problem = false;
				break;
			}
		}
		if(op_level == 2){
			int dist_lower_bound = minimum_dist_so_far + nn2hop_dist;
			double error_ratio =  (double)dist_lower_bound / dist_from_user[target_node];
			if(error_ratio >= 1.0){
				result = (double)(this->max_social_distance-dist_from_user[target_node])/this->max_social_distance;
				problem = false;
				//cout << "early terminate" << endl;
				break;
			}

			if(dist_lower_bound >= max_allowed_dist && dist_from_user[target_node] >= max_allowed_dist){
				//cout << "prunded using estimate for minimum relevance" << endl;
				problem = false;
				break;
			}
		}

		if(max_rel_so_far < min_relevance){
			//cout << "exceed minimum relevance" << endl;
			problem = false;
			break;
		}

		if(target_node == best_node){
			//cout << "minimum_dist_so_far: " << minimum_dist_so_far << endl;
			//cout << "found the node" << endl;
			result = max_rel_so_far;
			problem = false;
			break;
		}
		
		
	}
	//cout << "quit shortest path: " << endl;
	gettimeofday(&t2, NULL);
	// compute and print the elapsed time in millisec
	double oneTime = (t2.tv_sec - t1.tv_sec) * 1000.0;  // sec to ms
	oneTime += (t2.tv_usec - t1.tv_usec) / 1000.0; //  // us to ms
	elapsedTime += oneTime;

	if(oneTime > 50.0){
		cout << "node " << target_node << " takes a long" << endl;
		cout << "timing is: " << oneTime << " ^^^^^^^^^^^^^^^^^^^" << endl;
	}



	/*cout << "target node: " << target_node << " determined: " << dist_determined[target_node] <<  " with distance: " << dist_from_user[target_node] << endl;
	cout << "minimum relevance: " << min_relevance << endl;
	cout << "max_rel_so_far: " << max_rel_so_far << endl;
	cout << "num node processed: " << node_processed << endl;
	cout << "minimum_dist_so_far: " << minimum_dist_so_far << endl;
	cout << "time: " << elapsedTime << endl;
	cout << "xxxxxxxxxxxxxxxxxxxxxxxxxx" << endl;
	getchar();*/

	//cout << "exit node evalution: " << target_node << endl;
	if(problem){
		cout << "problem in shortest path" << endl;
		exit(1);
	}

	return result;
}